DROPS

Document

Density of Ideal Lattices

Authors: Johannes A. Buchmann and Richard Lindner

Published in: Dagstuhl Seminar Proceedings, Volume 9221, Algorithms and Number Theory (2009)

Abstract

The security of many emph{efficient} cryptographic constructions, e.g.~collision-resistant hash functions, digital signatures, and identification schemes, has been proven assuming the hardness of emph{worst-case} computational problems in ideal lattices. These lattices correspond to ideals in the ring of integers of some fixed number field $K$. In this paper we show that the density of $n$-dimensional ideal lattices with determinant $le b$ among all lattices under the same bound is in $O(b^{1-n})$. So for lattices of dimension $> 1$ with bounded determinant, the subclass of ideal lattices is always vanishingly small.

Cite as

Johannes A. Buchmann and Richard Lindner. Density of Ideal Lattices. In Algorithms and Number Theory. Dagstuhl Seminar Proceedings, Volume 9221, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{buchmann_et_al:DagSemProc.09221.2,
  author =	{Buchmann, Johannes A. and Lindner, Richard},
  title =	{{Density of Ideal Lattices}},
  booktitle =	{Algorithms and Number Theory},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9221},
  editor =	{Johannes A. Buchmann and John Cremona and Michael E. Pohst},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09221.2},
  URN =		{urn:nbn:de:0030-drops-21256},
  doi =		{10.4230/DagSemProc.09221.2},
  annote =	{Keywords: Post-quantum cryptography, provable security, ideal lattices}
}

Search Results

Documents authored by Lindner, Richard

Density of Ideal Lattices

Abstract

Cite as

Thanks for your feedback!

Could not send message